With the advent of technologies and services related to teleconferencing and digital image storage, considerable progress has been made in the field of digital signal processing. As will be appreciated by those skilled in the art, digital signal processing typically relates to systems, devices, and methodologies for generating a sampled data signal, compressing the signal for storage and/or transmission, and thereafter reconstructing the original data from the compressed signal. Critical to any highly efficient, cost effective digital signal processing system is the methodology used for achieving compression.
Methodologies capable of minimizing the amount of information necessary to represent and recover an original data are desirable, as well as those with lowest computational complexity and cost. In addition to cost, simplicity of hardware and software implementations capable of providing high quality data reproduction with minimal delay are likewise desirable.
To present, the next standard of JPEG 2000 (Joint Photographic Experts Group) systems for still images proposes algorithms, which use a wavelet to achieve spectral decomposition of an input signal. In systems utilizing a wavelet, the data is typically divided through low pass and high pass filters. The implementation of wavelet filters is typically achieved using a filter bank, and in many instances involves several levels of filtering preceded by decimation of the previous level results. Filter bank operation is often implemented through numerous multiplications and additions between the wavelet coefficients and the input data.
The typical wavelet is implemented as a full length filter. The disadvantage to the full length filter approach is that if a different wavelet is sought to be used for processing the various subband levels, an entirely new wavelet must be created. This may increase the number of operations, thereby increasing complexity, reducing efficiency, and lowering flexibility.
FIG. 1, is a block diagram of a prior art two-channel, single-level, digital data filter bank system 100. Multi-level, multi-channel systems also exist in the art. System 100 includes an encoder path 102 and a decoder path 104. The encoder path 102 includes an analysis bank 106 consisting of two complementary filters, a low pass-like filter H0(z) 108, and a high pass-like filter, H1(z), 110. The decoder path 104 includes a synthesis filter bank 112 consisting of a low pass-like filter G0(z) 114 and a high pass-like filter G1(z) 116. All filters are assumed to be causal, that is, the filters are dependent only on past or present samples and not on future samples. The filter banks 106, 112 exhibit signal processing delay which can be canceled out.
Any discrete wavelet transform used in two-channel sub-band filtering systems can be decomposed into a finite sequence of filtering steps denoted as cascades. The decomposition corresponds to a factorization of the polyphase matrix of the wavelet or sub-band filter into elementary matrices. These elementary matrices are formed as lower or upper triangular matrices, which have diagonal entries equal to a delay. Any matrix with polynomial entries can be decomposed (i.e. factored) into elementary matrices. Examples of this process are described in an article by Danbechies, I. and Sweldens, W., entitled "Factoring Wavelet Transforms into shifting Steps," J. Fourier Anal. Appl., Vol. 4, No. 3, pp. 245-267, 1998, which is incorporated herein by reference.
FIG. 2 is a block diagram of a two-channel filter bank 200 whose analysis and synthesis filters are represented in polyphase form. An analysis filter bank 202 is represented by a valid polyphase polynomial matrix H(z) having a determinant equal to a monomial in the variable "z", the algebraic equivalent of the delay operator, namely det [H(z)]=cz.sup.n, with an "n" integer and a "c" constant (ideally unity). The analysis filter bank 202 receives even-odd input data samples 206 separated by a unit delay 210 and generates low pass sub-band and high pass sub-band outputs 208. Based on the conditions set for the analysis filter bank 202, the synthesis filters 204 are represented by the inverse filter bank having a polyphase matrix G(z) equal to the adjoint of matrix H(z), that is adj [H(z)]. The output of the synthesis filter 204 generates polyphase outputs 212 separated by another delay 214, and which are recombined to obtain the original signal. FIG. 2 describes a lossless system; in other words, one not involving processing such as quantization, coding, error correction, or channel transmission loss.
The adjoint of matrix H(z),that is adj [H(z)], provides the condition to meet perfect reconstruction capability. It is well known that the inverse of a matrix is the adjoint of that matrix divided by its determinant. For example, if x(z), y(z), q(z), and p(z) are polynomials in "z", the general polyphase matrices for the analysis and synthesis ##EQU1##
filters for a two-channel case are:
with the polynomials meeting: EQU x(z)p(z)+y(z)q(z)=Z.sup.n. (2)
This last equation may be referred to as the Bezout identity, forcing the determinant of the H(z) matrix to be a delay. Thus, G(z)H(z) will also be a delay ensuring perfect reconstruction of the input assuming no quantization (image compression) and lossless channel. From here, the analysis and synthesis filters can be related as: EQU G0(z)=-H1(-z) and G1(z)=H0(-z). (3)
Hence, the following zero moments are obtained: EQU G0(-1)=-H1(1)=0 and G1(1)=H0(-1)=0. (4)
The matrices of equation (1) can be interchanged. Thus, the dual of equation (1) is the matrix pair: ##EQU2##
which interchanges the analysis with the synthesis filters in the following way: EQU H.sub.0 d(Z)=G.sub.0 (z). EQU H.sub.1 d(Z)=-G.sub.1 (z) (6)
For the most general case of bi-orthogonal filter banks which have the above properties, the interchange of the filters produces visible effects in the presence of quantization because of the different behavior (in time and frequency domains) of the two available low-pass filters which act as interpolators. This is more evident for some filter pairs where the filters are substantially different, such as the 2/6 pair where 2 represents the length of the low pass filter and 6 represents the length of the high pass filter. There are also differences in measured peak signal-to-noise ratio, even for similar pairs, such as the 7/9 pair(and its dual, the 9/7 pair).
There is a need for a method and apparatus, which provide improved wavelet filtering. A system having the flexibility to generate multiplierless filters without having to create an entirely new filter for each wavelet level would be highly desirable. Such wavelets would minimize computational intensity and improve system programming.